1. Field of the Invention
The present invention relates to an optical flow estimation method, an image synthesis method, an image synthesizer, a recording medium on which an image synthesis program is recorded, a digital camera, and a printer.
2. Description of the Prior Art
A technique for calculating optical flow from two images, and registering the two images on the basis of the obtained optical flow has been known. Description is now made of a conventional method of calculating optical flow.
(1) Lucas-Kanade Method
A large number of methods of calculating apparent optical flow of a moving object in a moving image have been conventionally proposed. The Lucas-Kanade method which is a local gradient method out of the methods is one of the best methods. The reason for this is that the speed of processing is high, implementing is easy, and the result has confidence.
As for the details of the Lucas-Kanade method, see an article: B. Lucas and T. Kanade, xe2x80x9cAn Iterative Image Registration Technique with an Application to Stereo Visionxe2x80x9d, In Seventh International Joint Conference on Artificial Intelligence (IJCAI-81), pp.674-979, 1981.
The outline of the Lucas-Kanade method will be described.
When a gray scale pattern I(x, y, t) of image coordinates p=(x, y) at time t is moved to coordinates (x+xcex4x, y+xcex4y) with its gradation distribution kept constant after a very short time period (xcex4t), the following optical flow constraint equation (1) holds:                                                                         ∂                I                                            ∂                x                                      ⁢                                          δ                ⁢                                  xe2x80x83                                ⁢                x                                            δ                ⁢                                  xe2x80x83                                ⁢                t                                              +                                                    ∂                I                                            ∂                y                                      ⁢                                          δ                ⁢                                  xe2x80x83                                ⁢                y                                                              xe2x80x83                                ⁢                                  δ                  ⁢                                      xe2x80x83                                    ⁢                  t                                                              +                                    ∂              I                                      ∂              t                                      =        0                            (        1        )            
In order to calculate optical flow {(v=(xcex4x/xcex4t, xcex4y/xcex4t)=(u, v)} in a two-dimensional image, the number of unknown parameters is two, so that another constraint equation is required. Lucas and Kanade have assumed that optical flow is constant in a local region of an identical object.
Suppose optical flow is constant within a local region xcfx89 on an image, for example. In this case, a squared error E of a gray scale pattern to be minimized can be defined by the following equation (2) when the following substitutions are made:
I0(P)=I(x,y,t),I1(p+v)=I(x+u,y+v,t+xcex4t)
                    E        =                              ∑            ω                    ⁢                                    [                                                                    I                    1                                    ⁡                                      (                                          p                      +                      v                                        )                                                  -                                                      I                    0                                    ⁡                                      (                    p                    )                                                              ]                        2                                              (        2        )            
When v is very small, the terms of second and higher degrees in Taylor""s expansion can be ignored, so that the relationship expressed by the following equation (3) holds:
I1(p+v)I1(p)+g(p)vxe2x80x83xe2x80x83(3)
where g(p) is a linear differential of I1(p).
The error E is minimized when the derivative of E with respect to v is zero, so that the relationship expressed by the following equation (4) holds:                                                         0              =                              xe2x80x83                            ⁢                                                ∂                                      ∂                    v                                                  ⁢                E                                                                                        ≈                              xe2x80x83                            ⁢                                                ∂                                      ∂                    v                                                  ⁢                                                      ∑                    ω                                    ⁢                                                            [                                                                                                    I                            1                                                    ⁡                                                      (                            p                            )                                                                          +                                                                              g                            ⁡                                                          (                              p                              )                                                                                ⁢                          v                                                -                                                                              I                            0                                                    ⁡                                                      (                            p                            )                                                                                              ]                                        2                                                                                                                          =                              xe2x80x83                            ⁢                                                ∑                  ω                                ⁢                                  2                  ⁢                                                            g                      ⁡                                              (                        p                        )                                                              ⁡                                          [                                                                                                    I                            1                                                    ⁡                                                      (                            p                            )                                                                          +                                                                              g                            ⁡                                                          (                              p                              )                                                                                ⁢                          v                                                -                                                                              I                            0                                                    ⁡                                                      (                            p                            )                                                                                              ]                                                                                                                              (        4        )            
Therefore, the optical flow v is found by the following equation (5):                     v        ≈                                            ∑              ω                        ⁢                                          g                ⁡                                  (                  p                  )                                            ⁡                              [                                                                            I                      0                                        ⁡                                          (                      p                      )                                                        -                                                            I                      1                                        ⁡                                          (                      p                      )                                                                      ]                                                                        ∑              ω                        ⁢                                          g                ⁡                                  (                  p                  )                                            2                                                          (        5        )            
Furthermore, the optical flow can be found with high precision by Newton-Raphson iteration, as expressed by the following equation (6):                               v                      k            +            1                          =                              v            k                    +                                    ∑                                                g                  k                                ⁡                                  [                                                            I                      0                                        -                                          I                      1                      k                                                        ]                                                                    ∑                                                (                                      g                    k                                    )                                2                                                                        (        6        )            
where I1k=I1(p+vk), gk=g(p+vk), I0=I0(p)
(2) Hierarchical Estimation Method
The largest problem of the gradient methods, including the Lucas-Kanade method, is that they cannot be applied to large motion because a good initial value is required. Therefore, a method of producing images respectively having resolutions which are different at several levels like a pyramid hierarchical structure to solve the problem has been conventionally proposed.
Images having resolutions which are different at several levels are first previously produced from each of two consecutive images. Approximate optical flow is then calculated between the images having the lowest resolution. More precise optical flow is calculated between the images having a resolution which is higher by one level. The processing is successively repeated until optical flow is calculated between the images having the highest resolution.
FIG. 1d, FIG. 1c, FIG. 1b, and FIG. 1a respectively illustrate an original image, an image having lower resolution than that of the original image shown in FIG. 1d, an image having lower resolution than that of the image having low resolution shown in FIG. 1c, and an image having lower resolution than that of the image having low resolution shown in FIG. 1b. In FIGS. 1a to 1d, S indicates one patch.
The optical flow is gradually found from the image shown in FIG. 1a (an image in a hierarchy 1) the image shown in FIG. 1b (an image in a hierarchy 2), the image shown in FIG. 1c (an image in a hierarchy 3) and the image shown in FIG. 1d (an image in a hierarchy 4) in this order. In FIGS. 1a to 1d, an arrow indicates an optical flow vector found for each patch.
However, the problem is that in a real image, there are few regions containing sufficient texture, so that reliable optical flow is not obtained.
A technique for affixing a plurality of images to one another and synthesizing the images to obtain a seamless image having a wide field of view and having high resolution (image mosaicking) has been conventionally actively studied. Classical applications include synthesis of aerial photographs or satellite photographs. In recent years, a method of synthesizing a plurality of digital images to obtain a seamless panoramic image, constructing a virtual reality environment has been paid attention to.
The following two methods have been known as a technique for obtaining a panoramic image by synthesis.
The first method is a method of translating a camera to previously pick up a plurality of images. The plurality of images obtained are simultaneously displayed on a monitor by a personal computer. A user designates corresponding points between the two images, to synthesize the two images.
In the first method, the motion of the camera is restricted to translation. In the first method, the user must designate the corresponding points.
The second method is a method of fixing a camera to a tripod and restricting the motion of the camera to only rotation on a horizontal surface, to pick up a plurality of images. The plurality of images obtained are projected on a cylindrical surface, to synthesize the images (see U.S. Pat. No. 5,396,583).
In the second method, the motion of the camera must be restricted to only rotation on a horizontal surface. Further, the focal length of the camera must be measured.
An object of the present invention is to provide an optical flow estimation method in which reliable optical flow is obtained even when an image region is hardly textured.
Another object of the present invention is to provide an image synthesis method, an image synthesizer, and a recording medium on which an image synthesis program is recorded, in which a seamless panoramic image can be obtained from a plurality of images , a camera is allowed to freely moving in order to pick up the plurality of images, and the focal length need not be measured.
Still another object of the present invention is to provide a digital camera or a printer having an image synthesis function capable of obtaining a seamless panoramic image from a plurality of images, allowing a camera to freely moving in order to pick up the plurality of images, and eliminating the necessity of measuring the focal length.
An optical flow estimation method is characterized by being so adapted as to calculate optical flow for each patch on the basis of two images, separate a region having low confidence and a region having high confidence depending on confidence of the optical flow, and interpolate the optical flow in the region having low confidence using the optical flow in its surrounding regions.
Confidence xcex3 is found, upon calculating from a 2xc3x972 matrix of coefficients G in the following equation (7) having as elements the squares of differentials in the vertical and horizontal directions of an image region xcfx89 its eigenvalues, by the following equation (8) from the smaller eigenvalue xcexmin and a gray scale residual E between the regions after tracking:                     G        =                              ∑                          p              ∈              ω                                ⁢                                    g              ⁡                              (                p                )                                      ⁢                                          g                ⁡                                  (                  p                  )                                            T                                                          (        7        )                                γ        =                              λ            min                    E                                    (        8        )            
In an image synthesis method for synthesizing a first image and a second image, a first image synthesis method according to the present invention is characterized by comprising the first step of extracting from the first image a plurality of partial images which are effective for tracking by optical flow between the first image and the second image, as feature points, the second step of tracking a point on the second image corresponding to each of the feature points on the first image, on the basis of the optical flow between the two images, the third step of finding a transformation for finding, on the basis of each of the feature points on the first image and the corresponding point on the second image which is found in the second step, a position on the second image corresponding to each of points on the first image, or a position on the first image corresponding to each of points on the second image, and the fourth step of synthesizing the first image and the second image such that the corresponding points on the first image and the second image coincide with each other on the basis of the obtained transformation.
The first step, for example, comprises the steps of extracting an overlapped portion of the first image and the second image, and extracting from the overlapped portion with the second image, on the first image, a plurality of the partial images which are effective for tracking by the optical flow between the two images, as the feature points.
In the step of extracting the overlapped portion of the first image and the second image, the overlapped portion of the first image and the second image is extracted on the basis of the SSD method, for example.
The second step, for example, comprises the steps of finding the optical flow from the first image and the second image on the basis of an optical flow estimation method using the hierarchically structured Lucas-Kanade method for interpolating optical flow having low confidence out of optical flows obtained in the respective stages of the optical flow estimation method using optical flow in its surrounding regions, and tracking the point on the second image corresponding to each of the feature points on the first image, on the basis of the obtained optical flow.
In an image synthesis method in which from three or more images from a first image to a n-th image (n is an integer of not less than three), the first image and the n-th image are synthesized, with the first image as a reference image, a second image synthesis method according to the present invention is characterized by comprising the first step of finding transformations for finding a position on an i-th image corresponding to each of points on an (i+1)-th image, taking i as each of integers from 1 to (nxe2x88x921), the second step of finding a transformation for finding a position on the first image corresponding to each of points on the n-th image, on the basis of all of the transformations found in the first step, and the third step of synthesizing the first image and the n-th image such that the corresponding points of the first image and the n-th image coincide with each other, wherein the first step repeats the following steps a to c, by updating i by 1 from i=1 up to i=(nxe2x88x921):
step a of extracting from the i-th image a plurality of partial images which are effective for tracking by optical flow between the i-th image and the (i+1)-th image, as feature points,
step b of tracking a point on the (i+1)-th image corresponding to each of the feature points on the i-th image on the basis of the optical flow between the two images, and
step c of finding a transformation for finding a position on the i-th image corresponding to each of points on the (i+1)-th image on the basis of each of the feature points on the i-th image and the corresponding point on the (i+1)-th image found in the step b.
In an image synthesis method for synthesizing three or more images from a first image to a n-th image (n is an integer of not less than three), with the first image as a reference image, a third image synthesis method according to the present invention is characterized by comprising the first step of finding transformations for finding a position on an i-th image corresponding to each of points on an (i+1)-th image, taking i as each of integers from 1 to (nxe2x88x921), the second step of finding, for each of images from a second image to the n-th image, a transformation for finding a position on the first image corresponding to each of points on each of the second to n-th images, on the basis of the transformations found in the first step, and the third step of performing such processes as synthesizing the first image and the second image on the basis of the transformation for finding the position on the first image corresponding to each of the points on the second image and synthesizing the third image and the synthesized image of the first and second images on the basis of the transformation for finding the position on the first image corresponding to each of the points on the third image, and continuing such processes up until the n-th image and the synthesized image of the first to (nxe2x88x921)-th images are synthesized on the basis of the transformation for finding the position on the first image corresponding to each of the points on the n-th image, thereby to obtain the synthesized image of the first to n-th images, wherein the first step repeats the following steps a to c, by updating i by 1 from i=1 up to i=(nxe2x88x921):
step a of extracting from the i-th image a plurality of partial images which are effective for tracking by optical flow between the i-th image and the (i+1)-th image, as feature points;
step b of tracking a point on the (i+1)-th image corresponding to each of the feature points on the i-th image on the basis of the optical flow between the two images; and
step c of finding a transformation for finding a position on the i-th image corresponding to each of points on the (i+1)-th image on the basis of each of the feature points on the i-th image and the corresponding point on the (i+1)-th image found in the step b.
The step a, for example, comprises the steps of extracting an overlapped portion of the i-th image and the (i+1)-th image, and extracting from the overlapped portion with the (i+1)-th image on the i-th image a plurality of the partial images which are effective for tracking by the optical flow between the two images, as the feature points.
In the step of extracting the overlapped portion of the i-th image and the (i+1)-th image, the overlapped portion of the i-th image and the (i+1)-th image is extracted on the basis of the SSD method, for example.
The step b, for example, comprises the steps of finding the optical flow from the i-th image and t the (i+1)-th image on the basis of an optical flow estimation method using the hierarchically structured Lucas-Kanade method for interpolating optical flow having low confidence out of optical flows obtained in the respective stages of the optical flow estimation method using optical flow in its surrounding regions, and tracking the point on the (i+1)-th image corresponding to each of the feature points on the i-th image, on the basis of the obtained optical flow.
In an image synthesizer for synthesizing a first image and a second image, a first image synthesizer according to the present invention is characterized by comprising first means for extracting from the first image a plurality of partial images which are effective for tracking by optical flow between the first image and the second image, as feature points, second means for tracking a point on the second image corresponding to each of the feature points on the first image, on the basis of the optical flow between the two images, third means for finding a transformation for finding, on the basis of each of the feature points on the first image and the corresponding point on the second image which is found by the second means, a position on the second image corresponding to each of points on the first image, or a position on the first image corresponding to each of points on the second image, and fourth means for synthesizing the first image and the second image such that the corresponding points on the first image and the second image coincide with each other on the basis of the obtained transformation.
The first means, for example, comprises means for extracting an overlapped portion of the first image and the second image, and means for extracting from the overlapped portion with the second image, on the first image, a plurality of the partial images which are effective for tracking by the optical flow between the two images, as the feature points.
The means for extracting the overlapped portion of the first image and the second image extracts the overlapped portion of the first image and the second image on the basis of the SSD method, for example.
The second means, for example, comprises means for finding the optical flow from the first image and the second image on the basis of an optical flow estimation method using the hierarchically structured Lucas-Kanade method for interpolating optical flow having low confidence out of optical flows obtained in the respective stages of the optical flow estimation method using optical flow in its surrounding regions, and means for tracking the point on the second image corresponding to each of the feature points on the first image, on the basis of the obtained optical flow.
In an image synthesizer in which from three or more images from a first image to a n-th image (n is an integer of not less than three), the first image and the n-th image are synthesized, with the first image as a reference image, a second image synthesizer according to the present invention is characterized by comprising first means for finding transformations for finding a position on an i-th image corresponding to each of points on an (i+1)-th image, taking i as each of integers from 1 to (nxe2x88x921), second means for finding a transformation for finding a position on the first image corresponding to each of points on the n-th image, on the basis of all of the transformations found by the first means, and third means for synthesizing the first image and the n-th image such that the corresponding points of the first image and the n-th image coincide with each other, wherein the first means repeats the following steps a to c, by updating i by 1 from i=1 up to i=(nxe2x88x921)
step a of extracting from the i-th image a plurality of partial images which are effective for tracking by optical flow between the i-th image and the (i+1)-th image, as feature points;
step b of tracking a point on the (i+1)-th image corresponding to each of the feature points on the i-th image on the basis of the optical flow between the two images; and
step c of finding a transformation for finding a position on the i-th image corresponding to each of points on the (i+1)-th image on the basis of each of the feature points on the i-th image and the corresponding point on the (i+1)-th image found in the step b.
In an image synthesizer for synthesizing three or more images from a first image to a n-th image (n is an integer of not less than three), with the first image as a reference image, a third image synthesizer according to the present invention is characterized by comprising first means for finding transformations for finding a position on an i-th image corresponding to each of points on an (i+1)-th image, taking i as each of integers from 1 to (nxe2x88x921) second means for finding, for each of images from a second image to the n-th image a transformation for finding a position on the first image corresponding to each of points on each of the second to n-th images on the basis of the transformations found by the first means, and third means for performing such processes as synthesizing the first image and the second image on the basis of the transformation for finding the position on the first image corresponding to each of the points on the second image and synthesizing the third image and the synthesized image of the first and second images on the basis of the transformation for finding the position on the first image corresponding to each of the points on the third image, and continuing such processes up until the n-th image and the synthesized image of the first to (nxe2x88x921)-th images are synthesized on the basis of the transformation for finding the position on the first image corresponding to each of the points on the n-th image, thereby to obtain the synthesized image of the first to n-th images, wherein the first means repeats the following steps a to c , by updating i by 1 from i=1 up to i=(nxe2x88x921)
step a of extracting from the i-th image a plurality of partial images which are effective for tracking by optical f low between the i-th image and the (i+1)-th image, as feature points;
step b of tracking a point on the (i+1)-th image corresponding to each of the feature points on the i-th image on the basis of the optical flow between the two images; and
step c of finding a transformation for finding a position on the i-th image corresponding to each of points on the (i+1)-th image on the basis of each of the feature points on the i-th image and the corresponding point on the (i+1)-th image found in the step b.
The step a, for example, comprises the steps of extracting an overlapped portion of the i-th image and the (i+1)-th image, and extracting from the overlapped portion with the (i+1)-th image on the i-th image a plurality of the partial images which are effective for tracking by the optical flow between the two images, as the feature points.
In the step of extracting the overlapped portion of the i-th image and the (i+1)-th image, the overlapped portion of the i-th image and the (i+1)-th image is extracted on the basis of the SSD method, for example.
The step b, for example, comprises the steps of finding the optical flow from the i-th image and the (i+1)-th image on the basis of an optical flow estimation method using the hierarchically structured Lucas-Kanade method for interpolating optical flow having low confidence out of optical flows obtained in the respective stages of the optical flow estimation method using optical flow in its surrounding regions, and tracking the point on the (i+1)-th image corresponding to each of the feature points on the i-th image, on the basis of the obtained optical flow.
In a computer readable recording medium on which an image synthesis program for synthesizing a first image and a second image is recorded, a first computer readable recording medium according to the present invention is characterized in that the image synthesis program has a computer execute the following steps of the first step of extracting from the first image a plurality of partial images which are effective for tracking by optical flow between the first image and the second image, as feature points, the second step of tracking a point on the second image corresponding to each of the feature points on the first image, on the basis of the optical flow between the two images, the third step of finding a transformation for finding, on the basis of each of the feature points on the first image and the corresponding point on the second image which is found in the second step, a position on the second image corresponding to each of points on the first image, or a position on the first image corresponding to each of points on the second image, and the fourth step of synthesizing the first image and the second image such that the corresponding points on the first image and the second image coincide with each other on the basis of the obtained transformation.
The first step, for example, comprises the steps of extracting an overlapped portion of the first image and the second image, and extracting from the overlapped portion with the second image, on the first image, a plurality of the partial images which are effective for tracking by the optical flow between the two images, as the feature points.
In the step of extracting the overlapped portion of the first image and the second image, the overlapped portion of the first image and the second image is extracted on the basis of the SSD method, for example.
The second step, for example, comprises the steps of finding the optical flow from the first image and the second image on the basis of an optical flow estimation method using the hierarchically structured Lucas-Kanade method for interpolating optical flow having low confidence out of optical flows obtained in the respective stages of the optical flow estimation method using optical flow in its surrounding regions, and tracking the point on the second image corresponding to each of the feature points on the first image, on the basis of the obtained optical flow.
In a computer readable recording medium on which an image synthesis program for synthesizing, from three or more images from a first image to a n-th image (n is an integer of not less than three), the first image and the n-th image , with the first image as a reference image, is recorded, a second computer readable recording medium according to the present invention is characterized in that the image synthesis program has a computer execute the following steps of the first step of finding transformations for finding a position on an i-th image corresponding to each of points on an (i+1)-th image, taking i as each of integers from 1 to (nxe2x88x921) the second step of finding a transformation for finding a position on the first image corresponding to each of points on the n-th image, on the basis of all of the transformations found in the first step, and the third step of synthesizing the first image and the n-th image such that the corresponding points of the first image and the n-th image coincide with each other, on the basis of the obtained transformation, wherein the first step repeats the following steps a to c, by updating i by 1 from i=1 up to i=(nxe2x88x921):
step a of extracting from the i-th image a plurality of partial images which are effective for tracking by optical flow between the i-th image and the (i+1)-th image, as feature points;
step b of tracking a point on the (i+1)-th image corresponding to each of the feature points on the i-th image on the basis of the optical flow between the two images; and
step c of finding a transformation for finding a position on the i-th image corresponding to each of points on the (i+1)-th image on the basis of each of the feature points on the i-th image and the corresponding point on the (i+1)-th image found in the step b.
In a computer readable recording medium on which an image synthesis program for synthesizing, from three or more images from a first image to a n-th image (n is an integer of not less than three), the first image and the n-th image , with the first image as a reference image, is recorded, a third computer readable recording medium according to the present invention is characterized in that the image synthesis program has a computer execute the following steps of the first step of finding transformations for finding a position on an i-th image corresponding to each of points on an (i+1)-th image, taking i as each of integers from 1 to (nxe2x88x921), the second step of finding, for each of images from the second image to the n-th image, a transformation for finding a position on the first image corresponding to each of points on each of the second to n-th images, on the basis of the transformations found in the first step, and the third step of performing such processes as synthesizing the first image and the second image on the basis of the transformation for finding the position on the first image corresponding to each of the points on the second image and synthesizing the third image and the synthesized image of the first and second images on the basis of the transformation for finding the position on the first image corresponding to each of the points on the third image, and continuing such processes up until the n-th image and the synthesized image of the first to (nxe2x88x921)-th images are synthesized on the basis of the transformation for finding the position on the first image corresponding to each of the points on the n-th image, thereby to obtain the synthesized image of the first to n-th images, wherein the first step repeats the following steps a to c, by updating i by 1 from i=1 up to i=(nxe2x88x921)
step a of extracting from the i-th image a plurality of partial images which are effective for tracking by optical flow between the i-th image and the (i+1)-th image, as feature points;
step b of tracking a point on the (i+1)-th image corresponding to each of the feature points on the i-th image on the basis of the optical flow between the two images; and
step c of finding a transformation for finding a position on the i-th image corresponding to each of points on the (i+1)-th image on the basis of each of the feature points on the i-th image and the corresponding point on the (i+1)-th image found in the step b.
The step a, for example, comprises the steps of extracting an overlapped portion of the i-th image and the (i+1)-th image, and extracting from the overlapped portion with the (i+1)-th image on the i-th image a plurality of the partial images which are effective for tracking by the optical flow between the two images, as the feature points.
In the step of extracting the overlapped portion of the i-th image and the (i+1)-th image, the overlapped portion of the i-th image and the (i+1)-th image is extracted on the basis of the SSD method, for example.
The step b, for example, comprises the steps of finding the optical flow from the i-th image and the (i+1)-th image on the basis of an optical flow estimation method using the hierarchically structured Lucas-Kanade method for interpolating optical flow having low confidence out of optical flows obtained in the respective stages of the optical flow estimation method using optical flow in its surrounding regions, and tracking the point on the (i+1)-th image corresponding to each of the feature points on the i-th image, on the basis of the obtained optical flow.
In a digital camera with a function of synthesizing a first image and a second image, a digital camera according to the present invention is characterized by comprising first means for extracting from the first image a plurality of partial images which are effective for tracking by optical flow between the first image and the second image, as feature points, second means for tracking a point on the second image corresponding to each of the feature points on the first image, on the basis of the optical flow between the two images, third means for finding a transformation for finding, on the basis of each of the feature points on the first image and the corresponding point on the second image which is found by the second means, a position on the second image corresponding to each of points on the first image, or a position on the first image corresponding to each of points on the second image, and fourth means for synthesizing the first image and the second image such that the corresponding points on the first image and the second image coincide with each other, on the basis of the obtained transformation.
In a printer with a function of synthesizing a first image and a second image, a printer according to the present invention is characterized by comprising first means for extracting from the first image a plurality of partial images which are effective for tracking by optical flow between the first image and the second image, as feature points, second means for tracking a point on the second image corresponding to each of the feature points on the first image, on the basis of the optical flow between the two images, third means for finding a transformation for finding, on the basis of each of the feature points on the first image and the corresponding point on the second image which is found by the second means, a position on the second image corresponding to each of points on the first image, or a position on the first image corresponding to each of points on the second image, and fourth means for synthesizing the first image and the second image such that the corresponding points on the first image and the second image coincide with each other, on the basis of the obtained transformation.